// 82. 删除排序链表中的重复元素 II
// https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/

/**
 * 
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

输入：head = [1,1,1,2,3]
输出：[2,3]
 */

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// var deleteDuplicates = function (head) {
//     if (!head) {
//         return head;
//     }

//     // let newHead = head;
//     // 初始化操作
//     // 记录前两个元素
//     let headPointer = head;
//     let prevPrev = null;
//     let prev = head;
//     let prevValue = prev.val;

//     let cur = head;
//     while (cur.next) {
//         cur = cur.next;

//         if (cur.val == prevValue) {
//             // 断开cur和prev这两个键的链接
//             // 将prev的parent和cur的next相连
//             // 特殊情况，如果prev就是头节点，或者cur就是头结点，那头结点要移动到cur.next
//             if (headPointer === cur || headPointer === prev) {
//                 headPointer = cur.next;
//             }

//             if (prevPrev != null) {
//                 prevPrev.next = cur.next;
//             }
//             prev = prevPrev ? prevPrev : headPointer; // 为了下一个循环做准备
//         } else {
//             prevPrev = prev;
//             prev = cur;
//             prevValue = cur.val;
//         }
//     }

//     return headPointer;
// };

var deleteDuplicates = function (head) {
    if (!head) {
        return head;
    }

    // let newHead = head;
    // 初始化操作
    // 记录前两个元素
    let headPointer = head;
    let headIndex = 0;
    let level = 0;
    let prevPrev = null;
    let prev = head;
    let prevValue = prev.val;
    let prevValueCount = 1;

    let cur = head;
    while (cur.next) {
        level++;
        cur = cur.next;

        if (cur.val == prevValue) {
            prevValueCount += 1;
        } else {
            if (prevValueCount >= 2) {
                if (prevPrev != null) {
                    prevPrev.next = cur;
                    prev = prevPrev;
                }

                if (level - prevValueCount <= headIndex) {
                    headPointer = cur;
                    headIndex = level;

                    if (prev.val === prevPrev) {
                        prev = null;
                    }
                }
                flat(headPointer);
            }

            prevPrev = prev;
            prev = cur;
            prevValue = cur.val;
            prevValueCount = 1;
        }
    }

    if (prevValueCount >= 2) {
        if (prevPrev != null) {
            prevPrev.next = null;
        }

        if (level - prevValueCount + 1 <= headIndex) {
            return null;
        }
    }

    return headPointer;
};

function listNode(arr) {
    console.log(`[listNode] arr is ${JSON.stringify(arr)}`);
    if (!arr || arr.length < 1) {
        return null;
    }

    let ret = {
        val: null,
        next: null,
    };
    let temp = ret;
    for (let i = 0; i < arr.length; i++) {
        temp.val = arr[i];
        temp.next = null;
        if (i < arr.length - 1) {
            temp.next = {
                val: null,
                next: null,
            };
        }

        temp = temp.next;
    }
    // console.log(`[listNode complete] ret is ${JSON.stringify(ret)}`);
    return ret;
}

function flat(listNode) {
    if (listNode == null) {
        console.log(`flat: node is ${JSON.stringify([])}`);
        return [];
    }

    let arr = [];
    let node = listNode;
    // console.log(`flat: node is ${JSON.stringify(node)}`);
    do {
        arr.push(node.val);
        node = node.next;
    } while (!!node && !!node.next);
    if (!!node) {
        arr.push(node.val);
    }

    console.log(`flat complete: arr is ${JSON.stringify(arr)}`);
    return arr;
}

/**
 * 输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
 */

flat(deleteDuplicates(listNode([1, 2, 3, 3, 4, 4, 5])));
flat(deleteDuplicates(listNode([1, 1, 1, 2, 3])));
flat(deleteDuplicates(listNode([1, 1, 1, 1])));
flat(deleteDuplicates(listNode([1, 1, 2, 2])));
flat(deleteDuplicates(listNode([1, 2, 2])));
flat(deleteDuplicates(listNode([1, 2, 2, 2])));
